{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct the Lexicographically Largest Valid Sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: constructDistancedSequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构建字典序最大的可行序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，请你找到满足下面条件的一个序列：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>整数 <code>1</code> 在序列中只出现一次。</li>\n",
    "\t<li><code>2</code> 到 <code>n</code> 之间每个整数都恰好出现两次。</li>\n",
    "\t<li>对于每个 <code>2</code> 到 <code>n</code> 之间的整数 <code>i</code> ，两个 <code>i</code> 之间出现的距离恰好为 <code>i</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>序列里面两个数 <code>a[i]</code> 和 <code>a[j]</code> 之间的 <strong>距离</strong> ，我们定义为它们下标绝对值之差 <code>|j - i|</code> 。</p>\n",
    "\n",
    "<p>请你返回满足上述条件中 <strong>字典序最大</strong> 的序列。题目保证在给定限制条件下，一定存在解。</p>\n",
    "\n",
    "<p>一个序列 <code>a</code> 被认为比序列 <code>b</code> （两者长度相同）字典序更大的条件是： <code>a</code> 和 <code>b</code> 中第一个不一样的数字处，<code>a</code> 序列的数字比 <code>b</code> 序列的数字大。比方说，<code>[0,1,9,0]</code> 比 <code>[0,1,5,6]</code> 字典序更大，因为第一个不同的位置是第三个数字，且 <code>9</code> 比 <code>5</code> 大。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 3\n",
    "<b>输出：</b>[3,1,2,3,2]\n",
    "<b>解释：</b>[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 5\n",
    "<b>输出：</b>[5,3,1,4,3,5,2,4,2]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-the-lexicographically-largest-valid-sequence](https://leetcode.cn/problems/construct-the-lexicographically-largest-valid-sequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-the-lexicographically-largest-valid-sequence](https://leetcode.cn/problems/construct-the-lexicographically-largest-valid-sequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        self.res = []\n",
    "        path = [0] * (2 * n - 1)\n",
    "        def back(path, idx, seen):\n",
    "            if len(self.res) != 0:\n",
    "                return True\n",
    "            if idx == len(path):\n",
    "                self.res = deepcopy(path)\n",
    "                return True\n",
    "            if path[idx] > 0:\n",
    "                back(path, idx+1, seen)\n",
    "            else:\n",
    "                for num in range(n, 0, -1):\n",
    "                    if num in seen: continue\n",
    "                    if path[idx] == 0 and num == 1:\n",
    "                        path[idx] = num\n",
    "                        seen.add(num)\n",
    "                        if back(path, idx+1, seen): return True\n",
    "                        path[idx] = 0\n",
    "                        seen.remove(num)\n",
    "                    elif path[idx] == 0 and num > 1 and idx + num < len(path) and path[idx+num] == 0:\n",
    "                        path[idx] = path[idx+num] = num\n",
    "                        seen.add(num)\n",
    "                        if back(path, idx+1, seen): return True\n",
    "                        seen.remove(num)\n",
    "                        path[idx] = path[idx+num] = 0\n",
    "            return False\n",
    "        seen = set()\n",
    "        back(path, 0, seen)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        N = 2 * n - 1\n",
    "        ans = [0] * N\n",
    "        vis = [False] * (n + 1)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i >= N:\n",
    "                return True\n",
    "            if ans[i] != 0:\n",
    "                return dfs(i + 1)\n",
    "\n",
    "            j = n\n",
    "            while j >= 1:\n",
    "                if vis[j]:\n",
    "                    j -= 1\n",
    "                    continue\n",
    "                if j == 1:\n",
    "                    ans[i] = 1\n",
    "                    vis[1] = True\n",
    "                    if dfs(i + 1):\n",
    "                        return True\n",
    "                    ans[i] = 0\n",
    "                    vis[1] = False\n",
    "                    return False\n",
    "                else:\n",
    "                    if i + j >= N or ans[i + j] != 0:\n",
    "                        j -= 1\n",
    "                        continue\n",
    "                    ans[i] = j\n",
    "                    ans[i + j] = j\n",
    "                    vis[j] = True\n",
    "                    if dfs(i + 1):\n",
    "                        return True\n",
    "                    ans[i] = 0\n",
    "                    ans[i + j] = 0\n",
    "                    vis[j] = False\n",
    "                \n",
    "                j -= 1\n",
    "\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        def backtrack(pos):\n",
    "            if pos >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[pos] != 0:\n",
    "                return backtrack(pos + 1)\n",
    "            for i in range(n,0,-1):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                if i == 1:\n",
    "                    visited[1] = True\n",
    "                    res[pos] = 1\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    res[pos] = 0\n",
    "                    visited[1] = False\n",
    "                else:\n",
    "                    if pos + i >= 2 * n -1:\n",
    "                        continue\n",
    "                    if res[pos + i] != 0:\n",
    "                        continue\n",
    "                    visited[i] = True\n",
    "                    res[pos] = i\n",
    "                    res[pos + i] = i\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    res[pos] = 0\n",
    "                    res[pos + i] = 0\n",
    "                    visited[i] = False\n",
    "            return False\n",
    "\n",
    "        visited = [False] * (n + 1)\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        N = 2 * n - 1\n",
    "        ans = [0] * N\n",
    "        vis = [False] * (n + 1)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i >= N:\n",
    "                return True\n",
    "            if ans[i] != 0:\n",
    "                return dfs(i + 1)\n",
    "            j = n\n",
    "            for j in range(n, 0, -1):\n",
    "                if vis[j]:\n",
    "                    continue\n",
    "                if j == 1:\n",
    "                    ans[i] = 1\n",
    "                    vis[1] = True\n",
    "                    if dfs(i + 1):\n",
    "                        return True\n",
    "                    ans[i] = 0\n",
    "                    vis[1] = False\n",
    "                    return False\n",
    "                else:\n",
    "                    if i + j >= N or ans[i + j] != 0:\n",
    "                        continue\n",
    "                    ans[i] = j\n",
    "                    ans[i + j] = j\n",
    "                    vis[j] = True\n",
    "                    if dfs(i + 1):\n",
    "                        return True\n",
    "                    ans[i] = 0\n",
    "                    ans[i + j] = 0\n",
    "                    vis[j] = False\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        sequence = [-1] * (2 * n - 1)\n",
    "        used_num = set()\n",
    "\n",
    "        def dfs(idx):\n",
    "            nonlocal sequence, used_num\n",
    "\n",
    "            if idx == 2 * n - 1:\n",
    "                return True\n",
    "            \n",
    "            if sequence[idx] != -1:\n",
    "                return dfs(idx + 1)\n",
    "            \n",
    "            for i in range(n, 0, -1):\n",
    "                if i in used_num:\n",
    "                    continue\n",
    "\n",
    "                gap = i if i != 1 else 0\n",
    "                if idx + gap < 2 * n - 1 and sequence[idx] == sequence[idx + gap] == -1:\n",
    "                    used_num.add(i)\n",
    "                    sequence[idx] = sequence[idx + gap] = i\n",
    "                    if dfs(idx + 1):\n",
    "                        return True\n",
    "\n",
    "                    used_num.remove(i)\n",
    "                    sequence[idx] = sequence[idx + gap] = -1\n",
    "        \n",
    "        dfs(0)\n",
    "        return sequence\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        \n",
    "        def backtrace(i: int) -> bool:\n",
    "            if i >= 2 * n - 1:  # 如果成功排列到最后一个数，则说明成功。\n",
    "                return True\n",
    "            if res[i] != 0:  # 如果当前i位置已经有数了，则继续判断i+1的位置。\n",
    "                return backtrace(i + 1)\n",
    "            for x in range(n, 0, -1):  # 要求字典序最大，则倒序选择。\n",
    "                if visited[x] == True:  # 用了的数不再用。\n",
    "                    continue\n",
    "                if x == 1:       #1只出现1次，要单独判断\n",
    "                    visited[1] = True       #借\n",
    "                    res[i] = 1              #借\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0              #回溯==有借有还\n",
    "                    visited[1] = False      #回溯\n",
    "                else:\n",
    "                    if i + x >= 2 * n - 1:\n",
    "                        continue\n",
    "                    if res[i] != 0 or res[i + x] != 0:\n",
    "                        continue\n",
    "                    res[i] = x              #借\n",
    "                    res[i + x] = x          #借\n",
    "                    visited[x] = True       #借\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    visited[x] = False      #回溯==有借有还\n",
    "                    res[i + x] = 0          #回溯\n",
    "                    res[i] = 0              #回溯\n",
    "            return False\n",
    "        \n",
    "        backtrace(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        def backtrack(pos):\n",
    "            if pos >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[pos] != 0:\n",
    "                return backtrack(pos + 1)\n",
    "            for i in range(n,0,-1):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                if i == 1:\n",
    "                    visited[1] = True\n",
    "                    res[pos] = 1\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    res[pos] = 0\n",
    "                    visited[1] = False\n",
    "                else:\n",
    "                    if pos + i >= 2 * n -1 or res[pos + i] != 0:\n",
    "                        continue\n",
    "                    visited[i] = True\n",
    "                    res[pos] = i\n",
    "                    res[pos + i] = i\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    res[pos] = 0\n",
    "                    res[pos + i] = 0\n",
    "                    visited[i] = False\n",
    "            return False\n",
    "\n",
    "        visited = [False] * (n + 1)\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "\n",
    "        def dfs(i):\n",
    "            if i >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[i] != 0:\n",
    "                return dfs(i+1)\n",
    "            for x in range(n, 0, -1):\n",
    "                if visited[x]:\n",
    "                    continue\n",
    "                if x == 1:\n",
    "                    res[i] = x\n",
    "                    visited[x] = True\n",
    "                    if dfs(i+1):\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    visited[x] = False\n",
    "                else:\n",
    "                    if i + x >= 2 * n - 1:\n",
    "                        continue\n",
    "                    if res[i+x] != 0:\n",
    "                        continue\n",
    "                    res[i] = x\n",
    "                    res[i+x] = x\n",
    "                    visited[x] = True\n",
    "                    if dfs(i+1):\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    res[i+x] = 0\n",
    "                    visited[x] = False\n",
    "            return False\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ln = n*2-1\n",
    "        ans = [0] * ln\n",
    "        used = [False] * (n+1)\n",
    "\n",
    "        def trace_back(i):\n",
    "            if i >= ln:\n",
    "                return True \n",
    "            if ans[i] > 0:\n",
    "                return trace_back(i+1)         \n",
    "            for x in range(n,0,-1):\n",
    "                if used[x]:\n",
    "                    continue  \n",
    "                if x == 1:\n",
    "                    used[x] = True \n",
    "                    ans[i] = x \n",
    "                    if trace_back(i+1):\n",
    "                        return True \n",
    "                    used[x] = False \n",
    "                    ans[i] = 0\n",
    "                else:\n",
    "                    if i+x >= ln or ans[i+x] > 0:\n",
    "                        continue\n",
    "                    used[x] = True \n",
    "                    ans[i] = ans[i+x] = x \n",
    "                    if trace_back(i+1):\n",
    "                        return True \n",
    "                    used[x] = False \n",
    "                    ans[i] = ans[i+x] = 0\n",
    "            return False  \n",
    "\n",
    "        trace_back(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        if n==1:\n",
    "            return [1]\n",
    "        result = [None]*(2*n-1)\n",
    "        used_n = [True]*(n+1)\n",
    "\n",
    "        def traversal(index):\n",
    "            while True:\n",
    "                if index == 2*n-1:\n",
    "                    return True\n",
    "                if result[index] is None:\n",
    "                    break\n",
    "                index += 1\n",
    "\n",
    "\n",
    "            for cur_n in range(n-1, 0, -1):                            \n",
    "                if (used_n[cur_n]) and ((cur_n==1) or ((index+cur_n<2*n-1) and (result[index+cur_n] is None))):\n",
    "                    result[index] = cur_n\n",
    "                    used_n[cur_n] = False\n",
    "                    if cur_n != 1:\n",
    "                        result[index+cur_n] = cur_n\n",
    "                    if traversal(index+1):\n",
    "                        return True\n",
    "                    result[index] = None\n",
    "                    used_n[cur_n] = True\n",
    "                    if cur_n != 1:\n",
    "                        result[index+cur_n] = None\n",
    "            return False\n",
    "        \n",
    "        result[0] = n\n",
    "        result[n] = n\n",
    "        used_n[-1] = False\n",
    "        traversal(1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        m = 2 * n - 1\n",
    "        ans = []\n",
    "        path = [0] * m\n",
    "        used = [False] * (n + 1)\n",
    "        def dfs(k):\n",
    "            nonlocal ans, used, path\n",
    "            if k >= m:\n",
    "                ans = path\n",
    "                return True\n",
    "            if path[k] != 0:\n",
    "                return dfs(k + 1)\n",
    "            for i in range(n, 0, -1):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                p = k if i == 1 else k + i\n",
    "                if p >= m:\n",
    "                    continue\n",
    "                if path[k] != 0 or path[p] != 0:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                path[k] = path[p] = i\n",
    "                if dfs(k + 1):\n",
    "                    return True\n",
    "                path[k] = path[p] = 0\n",
    "                used[i] = False\n",
    "            return False\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        length = n*2-1\n",
    "        array = [None] * length\n",
    "        candidates = [val for val in range(n,0,-1)]\n",
    "\n",
    "        def fillpositions(candidates, array): \n",
    "            if len(candidates)==0:\n",
    "                return True\n",
    "\n",
    "            # 找到第一个可填入的index\n",
    "            for i in range(len(array)):\n",
    "                if array[i] is None:\n",
    "                    index = i\n",
    "                    break\n",
    "\n",
    "            # 尝试所有数字\n",
    "            for i in range(len(candidates)):\n",
    "                val = candidates[i]\n",
    "                candidates_next = candidates[:i] + candidates[i+1:]\n",
    "                if array[index] is None:\n",
    "                    if val > 1:\n",
    "                        if index+val<len(array) and array[index+val] is None:\n",
    "                            array[index] = val\n",
    "                            array[index+val] = val\n",
    "                            # print(val, array, candidates_next)\n",
    "                            flag = fillpositions(candidates_next, array)\n",
    "                            if flag == True:\n",
    "                                return True\n",
    "                            array[index] = None\n",
    "                            array[index+val] = None\n",
    "                    else:\n",
    "                        array[index] = val\n",
    "                        # print(val, array, candidates_next)\n",
    "                        flag = fillpositions(candidates_next, array)\n",
    "                        if flag == True:\n",
    "                            return True\n",
    "                        array[index] = None\n",
    "            return False\n",
    "\n",
    "\n",
    "        fillpositions(candidates, array)\n",
    "        return array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        temp=[1]*(2*n-1)\n",
    "        self.check=False\n",
    "        ss=set()\n",
    "        def backtrack(i,s,res):\n",
    "            if i<2*n-1 and temp[i]>1:\n",
    "                backtrack(i+1,s,res)\n",
    "            if s==(2*n-1):\n",
    "                if res==n:\n",
    "                    self.check=True\n",
    "                    return temp\n",
    "            for k in range(n,0,-1):\n",
    "                if k==1 and k not in ss:\n",
    "                    ss.add(k)\n",
    "                    backtrack(i+1,s+1,res+1)\n",
    "                    if self.check:\n",
    "                        return temp\n",
    "                    if not self.check:\n",
    "                        ss.remove(k)\n",
    "                elif k not in ss and temp[i]==1 and i+k<(2*n-1) and temp[i+k]==1:\n",
    "                    temp[i]=temp[i+k]=k\n",
    "                    ss.add(k)\n",
    "                    backtrack(i+1,s+2,res+1)\n",
    "                    if self.check:\n",
    "                        return temp\n",
    "                    if not self.check:\n",
    "                        temp[i]=temp[i+k]=1\n",
    "                        ss.remove(k)\n",
    "            return temp\n",
    "        return backtrack(0,0,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int):\n",
    "        def dfs(pos):\n",
    "            if pos >= len(res):\n",
    "                return True\n",
    "            if res[pos] != 0: \n",
    "                return dfs(pos+1)\n",
    "                \n",
    "            for i in range(n, 0, -1):\n",
    "                if check[i] == 1: continue\n",
    "                if i == 1:\n",
    "                    check[1] = 1\n",
    "                    res[pos] = 1\n",
    "                    if dfs(pos+1): return True\n",
    "                    res[pos] = 0\n",
    "                    check[1] = 0\n",
    "                else:\n",
    "                    if i + pos >= len(res): continue\n",
    "                    if res[pos] != 0 or res[pos+i] != 0: continue\n",
    "                    check[i] = 1\n",
    "                    res[pos] = res[pos+i] = i\n",
    "                    if dfs(pos+1): return True\n",
    "                    res[pos] = res[pos+i] = 0\n",
    "                    check[i] = 0   \n",
    "            return False\n",
    "        res = [0] * (2 * n - 1)     \n",
    "        check = [0] * (n+1)\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        def backtrack(pos):\n",
    "            if pos >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[pos] != 0:\n",
    "                return backtrack(pos + 1)\n",
    "            for i in range(n,0,-1):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                if i == 1:\n",
    "                    visited[1] = True\n",
    "                    res[pos] = 1\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    visited[1] = False\n",
    "                    res[pos] = 0\n",
    "                    # return False\n",
    "                else:\n",
    "                    if pos + i >= 2 * n -1:\n",
    "                        continue\n",
    "                    if res[pos + i] != 0:\n",
    "                        continue\n",
    "                    res[pos] = i\n",
    "                    res[pos + i] = i\n",
    "                    visited[i] = True\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    res[pos] = 0\n",
    "                    res[pos + i] = 0\n",
    "                    visited[i] = False\n",
    "            return False\n",
    "\n",
    "        visited = [False] * (n + 1)\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        \n",
    "        def backtrace(i: int) -> bool:\n",
    "            if i >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[i] != 0:\n",
    "                return backtrace(i + 1)\n",
    "            for x in range(n, 0, -1):\n",
    "                if visited[x] == True:\n",
    "                    continue\n",
    "                if x == 1:       #1只出现1次，要单独判断\n",
    "                    visited[1] = True       #借\n",
    "                    res[i] = 1              #借\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0              #回溯==有借有还\n",
    "                    visited[1] = False      #回溯\n",
    "                else:\n",
    "                    if i + x >= 2 * n - 1:\n",
    "                        continue\n",
    "                    if res[i] != 0 or res[i + x] != 0:\n",
    "                        continue\n",
    "                    res[i] = x              #借\n",
    "                    res[i + x] = x          #借\n",
    "                    visited[x] = True       #借\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    visited[x] = False      #回溯==有借有还\n",
    "                    res[i + x] = 0          #回溯\n",
    "                    res[i] = 0              #回溯\n",
    "            return False\n",
    "        \n",
    "        backtrace(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        def backtrack(pos):\n",
    "            if pos >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[pos] != 0:\n",
    "                return backtrack(pos + 1)\n",
    "            for i in range(n,0,-1):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                if i == 1:\n",
    "                    visited[1] = True\n",
    "                    res[pos] = 1\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    visited[1] = False\n",
    "                    res[pos] = 0\n",
    "                    return False\n",
    "                else:\n",
    "                    if pos + i >= 2 * n -1:\n",
    "                        continue\n",
    "                    if res[pos + i] != 0:\n",
    "                        continue\n",
    "                    res[pos] = i\n",
    "                    res[pos + i] = i\n",
    "                    visited[i] = True\n",
    "                    if backtrack(pos + 1):\n",
    "                        return True\n",
    "                    res[pos] = 0\n",
    "                    res[pos + i] = 0\n",
    "                    visited[i] = False\n",
    "            return False\n",
    "\n",
    "        visited = [False] * (n + 1)\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        elif n == 2:\n",
    "            return [2, 1, 2]\n",
    "        else:\n",
    "            res = [n, n - 2] + [0] * (n * 2 - 3)\n",
    "            res[n] = n\n",
    "            if n > 3:\n",
    "                res[n - 1] = n - 2\n",
    "            rest = set(range(n))\n",
    "            rest.remove(n - 2)\n",
    "            self.dfs(2, res, n, rest)\n",
    "            return res\n",
    "    \n",
    "    def dfs(self, now, res, n, rest):\n",
    "        if now == n * 2 - 1:\n",
    "            return True\n",
    "        \n",
    "        if res[now]:\n",
    "            return self.dfs(now + 1, res, n, rest)\n",
    "\n",
    "        for num in range(n - 1, 1, -1):\n",
    "            if num in rest and now + num < n * 2 - 1 and res[now + num] == 0:\n",
    "                res[now] = res[now + num] = num\n",
    "                rest.remove(num)\n",
    "                if self.dfs(now + 1, res, n, rest):\n",
    "                    return True\n",
    "                rest.add(num)\n",
    "                res[now] = res[now + num] = 0\n",
    "        \n",
    "        if 1 in rest:\n",
    "            res[now] = 1\n",
    "            rest.remove(1)\n",
    "            if self.dfs(now + 1, res, n, rest):\n",
    "                return True\n",
    "            rest.add(1)\n",
    "            res[now] = 0\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        temp=[1]*(2*n-1)\n",
    "        self.check=False\n",
    "        ss=set()\n",
    "        def backtrack(i,s):\n",
    "            if i<2*n-1 and temp[i]>1:\n",
    "                backtrack(i+1,s)\n",
    "            if s==(2*n-1):\n",
    "                self.check=True\n",
    "                return temp\n",
    "            for k in range(n,0,-1):\n",
    "                if k==1 and k not in ss:\n",
    "                    ss.add(k)\n",
    "                    backtrack(i+1,s+1)\n",
    "                    if self.check:\n",
    "                        return temp\n",
    "                    if not self.check:\n",
    "                        ss.remove(k)\n",
    "                elif k not in ss and temp[i]==1 and i+k<(2*n-1) and temp[i+k]==1:\n",
    "                    temp[i]=temp[i+k]=k\n",
    "                    ss.add(k)\n",
    "                    backtrack(i+1,s+2)\n",
    "                    if self.check:\n",
    "                        return temp\n",
    "                    if not self.check:\n",
    "                        temp[i]=temp[i+k]=1\n",
    "                        ss.remove(k)\n",
    "            return temp\n",
    "        return backtrack(0,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        a = [0]*(2*n-1)\n",
    "        def f(i):\n",
    "            \n",
    "            if i == len(a):\n",
    "                return 1\n",
    "            if a[i] != 0:\n",
    "                return f(i+1)\n",
    "\n",
    "            for j in range(n, 0, -1):\n",
    "                if j not in a:\n",
    "                    if j == 1:\n",
    "                        if a[i] == 0:\n",
    "                            a[i] = j\n",
    "                            x = f(i+1)\n",
    "                            if x:\n",
    "                                return 1\n",
    "                            a[i] = 0\n",
    "                    else:\n",
    "                        if a[i] == 0 and i+j < len(a) and a[i+j] == 0:\n",
    "                            a[i] = j\n",
    "                            a[i+j] = j\n",
    "                            x = f(i+1)\n",
    "                            if x:\n",
    "                                return 1\n",
    "                            a[i] = 0\n",
    "                            a[i+j] = 0\n",
    "            return 0\n",
    "        f(0)\n",
    "        return a\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "\n",
    "        def backtrace(i) -> bool:\n",
    "            if i >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[i] != 0:\n",
    "                return backtrace(i + 1)\n",
    "\n",
    "            for x in range(n, 0, -1):\n",
    "                if visited[x] == True:\n",
    "                    continue\n",
    "                if x == 1:\n",
    "                    res[i] = 1\n",
    "                    visited[x] = True\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    visited[x] = False\n",
    "                else:\n",
    "                    if i + x >= 2 * n - 1:\n",
    "                        continue\n",
    "                    if res[i] != 0 or res[i + x] != 0:\n",
    "                        continue\n",
    "\n",
    "                    res[i] = x\n",
    "                    res[i + x] = x\n",
    "                    visited[x] = True\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    res[i + x] = 0\n",
    "                    visited[x] = False\n",
    "            return False\n",
    "\n",
    "        backtrace(0)\n",
    "        return res\n",
    "                    \n",
    "                \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n * 2 - 1)\n",
    "        arr = SortedList(_ for _ in range(-n, -1))\n",
    "        used_1 = False\n",
    "\n",
    "        def traceback(idx):\n",
    "            if idx == n * 2 - 1:\n",
    "                return True\n",
    "            if ans[idx]:\n",
    "                return traceback(idx + 1)\n",
    "            for num in arr:\n",
    "                if idx - num < n * 2 - 1 and ans[idx - num] == 0:\n",
    "                    ans[idx] = ans[idx - num] = -num\n",
    "                    arr.discard(num)\n",
    "                    if traceback(idx + 1):\n",
    "                        return True\n",
    "                    arr.add(num)\n",
    "                    ans[idx] = ans[idx - num] = 0\n",
    "            nonlocal used_1\n",
    "            if not used_1:\n",
    "                ans[idx] = 1\n",
    "                used_1 = True\n",
    "                if traceback(idx + 1):\n",
    "                    return True\n",
    "                ans[idx] = 0\n",
    "                used_1 = False\n",
    "            return False\n",
    "        traceback(0)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        m = (n - 1) * 2 + 1\n",
    "        ans = [-1] * m\n",
    "        def f(cur):\n",
    "            if cur == m:\n",
    "                return True\n",
    "            if ans[cur] != -1:\n",
    "                return f(cur + 1)\n",
    "            for i in range(n, 0, -1):\n",
    "                if i not in ans:\n",
    "                    g = i if i > 1 else 0\n",
    "                    if cur + g < m and ans[cur] == ans[cur + g] == -1:\n",
    "                        ans[cur] = ans[cur + g] = i\n",
    "                        if f(cur + 1):\n",
    "                            return True\n",
    "                        ans[cur] = ans[cur + g] = -1\n",
    "            return False\n",
    "        f(0)\n",
    "        return ans\n",
    "\n",
    "s = Solution()\n",
    "s.constructDistancedSequence(5)\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        \n",
    "#         i: pos\n",
    "        def backtrace(i):\n",
    "            if i >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[i] != 0:\n",
    "                return backtrace(i + 1)\n",
    "            \n",
    "            # x: number\n",
    "            for x in range(n, 0, -1):\n",
    "                if visited[x] == True:\n",
    "                    continue\n",
    "\n",
    "                if x == 1:\n",
    "                    visited[1] = True\n",
    "                    res[i] = 1\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    visited[1] = False\n",
    "                else:\n",
    "                    if i + x >= 2 * n - 1:\n",
    "                        continue\n",
    "                    if res[i] != 0 or res[i + x] != 0:\n",
    "                        continue\n",
    "                    res[i] = x\n",
    "                    res[i + x] = x\n",
    "                    visited[x] = True\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    res[i + x] = 0\n",
    "                    visited[x] = False\n",
    "            return False\n",
    "        \n",
    "        \n",
    "\n",
    "        backtrace(0)\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        length = n*2-1\n",
    "        array = [None] * length\n",
    "        candidates = [val for val in range(n,0,-1)]\n",
    "\n",
    "        def fillpositions(candidates, array): \n",
    "            if len(candidates)==0:\n",
    "                return True\n",
    "\n",
    "            # 找到第一个可填入的index\n",
    "            for i in range(len(array)):\n",
    "                if array[i] is None:\n",
    "                    index = i\n",
    "                    break\n",
    "\n",
    "            # 尝试所有数字\n",
    "            for i in range(len(candidates)):\n",
    "                val = candidates[i]\n",
    "                candidates_next = candidates[:i] + candidates[i+1:]\n",
    "                if array[index] is None:\n",
    "                    if val > 1:\n",
    "                        if index+val<len(array) and array[index+val] is None:\n",
    "                            array[index] = val\n",
    "                            array[index+val] = val\n",
    "                            # print(val, array, candidates_next)\n",
    "                            flag = fillpositions(candidates_next, array)\n",
    "                            if flag == True:\n",
    "                                return True\n",
    "                            array[index] = None\n",
    "                            array[index+val] = None\n",
    "                    else:\n",
    "                        array[index] = val\n",
    "                        # print(val, array, candidates_next)\n",
    "                        flag = fillpositions(candidates_next, array)\n",
    "                        if flag == True:\n",
    "                            return True\n",
    "                        array[index] = None\n",
    "            return False\n",
    "\n",
    "\n",
    "        fillpositions(candidates, array)\n",
    "        return array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n * 2 - 1)\n",
    "        arr = SortedList(_ for _ in range(-n, -1))\n",
    "        used_1 = False\n",
    "\n",
    "        def traceback(idx):\n",
    "            if idx == n * 2 - 1:\n",
    "                return True\n",
    "            if ans[idx]:\n",
    "                return traceback(idx + 1)\n",
    "            for num in arr:\n",
    "                if idx - num < n * 2 - 1 and ans[idx - num] == 0:\n",
    "                    ans[idx] = ans[idx - num] = -num\n",
    "                    arr.discard(num)\n",
    "                    if traceback(idx + 1):\n",
    "                        return True\n",
    "                    arr.add(num)   # 回溯\n",
    "                    ans[idx] = ans[idx - num] = 0\n",
    "            nonlocal used_1\n",
    "            if not used_1:\n",
    "                ans[idx] = 1\n",
    "                used_1 = True\n",
    "                if traceback(idx + 1):\n",
    "                    return True\n",
    "                ans[idx] = 0   # 回溯\n",
    "                used_1 = False\n",
    "            return False\n",
    "        \n",
    "        if traceback(0):    return ans\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        length = 2 * n - 1\n",
    "        res = [0] * length\n",
    "\n",
    "        def backtrack(i, used):\n",
    "            if i == length:\n",
    "                return True\n",
    "            if res[i]:\n",
    "                return backtrack(i + 1, used)\n",
    "            for num in range(n, 0, -1):\n",
    "                if not used[num] and (num == 1 or i + num < length and not res[i+num]):\n",
    "                    if num > 1:\n",
    "                        res[i+num] = num\n",
    "                    res[i] = num\n",
    "                    used[num] = True\n",
    "                    if backtrack(i + 1, used):\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    used[num] = False\n",
    "                    if num > 1:\n",
    "                        res[i+num] = 0\n",
    "            return False\n",
    "\n",
    "        backtrack(0, [False] * (n + 1))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        m = 2 * n - 1\n",
    "        f = [-1] * m \n",
    "        def dfs(i):\n",
    "            if i == m:\n",
    "                return True\n",
    "            if f[i] != -1:\n",
    "                return dfs(i + 1)\n",
    "            for x in range(n, 0, -1):\n",
    "                if x not in f:\n",
    "                    gap = x if x > 1 else 0\n",
    "                    if i + gap < m and f[i] == f[i + gap] == -1:\n",
    "                        f[i] = f[i + gap] = x \n",
    "                        if dfs(i + 1):\n",
    "                            return True\n",
    "                        f[i] = f[i + gap] = -1\n",
    "            return False\n",
    "        dfs(0)\n",
    "        return f        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:        \n",
    "        used = set()\n",
    "        res = [-1]*(2*n-1)\n",
    "        # 栈模拟递归\n",
    "        stack = [(0,n,False)] # (idx,val,is_post_process)，idx和val为每次递归的参数，在res的第idx位上填上val，is_post_procss表示是否需要结束递归的后处理\n",
    "        def process(idx,val,post): \n",
    "            # 前后处理合并，入栈时向res填上元素，标记为已使用\n",
    "            # 出栈时为后处理，撤销填入res的元素并标记为未使用\n",
    "            res[idx] = -1 if post else val\n",
    "            if val > 1: \n",
    "                res[idx+val] = -1 if post else val\n",
    "            if post: \n",
    "                used.remove(val)\n",
    "            else:    \n",
    "                used.add(val)\n",
    "        # 贪心地取最大的值，发现所有都使用就是结束的时候\n",
    "        while True:\n",
    "            idx,val,post = stack.pop() \n",
    "            if post:\n",
    "                process(idx,val,True) # 第二次见到该参数，说明要出栈模拟递归后处理\n",
    "            else:\n",
    "                stack.append((idx,val,True)) # 下次见到就要做后处理了\n",
    "                process(idx,val,False)       # 填入res，标记为已使用\n",
    "                if len(used) >= n: break     # 贪心，提前结束\n",
    "                while idx < len(res) and res[idx] != -1: \n",
    "                    idx += 1 # 可能出现下一个相邻idx已经有值，需要找下一个空位\n",
    "                for i in range(1,n+1):       # 从小到大，确保下次栈顶为最大值\n",
    "                    if i in used: continue   # 剪枝：不要已使用的\n",
    "                    if i > 1 and ((idx+i) >= len(res) or res[idx+i] != -1): continue # 剪枝：对于值大于1的，不要越界或已res上的位置已占用的\n",
    "                    stack.append((idx,i,False)) # 完成剪枝后可加入下次处理\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n*2-1)\n",
    "        used = [False] * (n+1)\n",
    "\n",
    "        def trace_back(i):\n",
    "            if i > 2*n-2:\n",
    "                return True \n",
    "            if ans[i] > 0:\n",
    "                return trace_back(i+1)         \n",
    "            for x in range(n,0,-1):\n",
    "                if used[x]:\n",
    "                    continue  \n",
    "                if x == 1:\n",
    "                    used[x] = True \n",
    "                    ans[i] = x \n",
    "                    if trace_back(i+1):\n",
    "                        return True \n",
    "                    used[x] = False \n",
    "                    ans[i] = 0\n",
    "                else:\n",
    "                    if i+x > 2*n-2 or ans[i+x] > 0:\n",
    "                        continue\n",
    "                    used[x] = True \n",
    "                    ans[i] = ans[i+x] = x \n",
    "                    if trace_back(i+1):\n",
    "                        return True \n",
    "                    used[x] = False \n",
    "                    ans[i] = ans[i+x] = 0\n",
    "            return False  \n",
    "\n",
    "        trace_back(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        def backtrace(i: int) -> bool:\n",
    "            if i >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[i] != 0:\n",
    "                return backtrace(i + 1)\n",
    "            for x in range(n, 0, -1):\n",
    "                if visited[x] == True:\n",
    "                    continue\n",
    "                if x == 1:       #1只出现1次，要单独判断\n",
    "                    visited[1] = True       #借\n",
    "                    res[i] = 1              #借\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0              #回溯==有借有还\n",
    "                    visited[1] = False      #回溯\n",
    "                else:\n",
    "                    if i + x >= 2 * n - 1:\n",
    "                        continue\n",
    "                    if res[i] != 0 or res[i + x] != 0:\n",
    "                        continue\n",
    "                    res[i] = x              #借\n",
    "                    res[i + x] = x          #借\n",
    "                    visited[x] = True       #借\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    visited[x] = False      #回溯==有借有还\n",
    "                    res[i + x] = 0          #回溯\n",
    "                    res[i] = 0              #回溯\n",
    "            return False\n",
    "        \n",
    "        backtrace(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "\n",
    "        lens = 2 * n - 1\n",
    "        ans = [0] * lens\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(start):\n",
    "            nonlocal n, lens\n",
    "            if len(visited) == n: return ans\n",
    "            # 当前位置已经填了，那就进行下一个吧\n",
    "            if ans[start] > 0: return dfs(start + 1)\n",
    "            # 贪心：数字从大到小填\n",
    "            for i in range(n, 0, -1):\n",
    "                if i in visited: continue\n",
    "                sec = start + i\n",
    "                if i == 1 or (sec < lens and ans[sec] == 0):\n",
    "                    visited.add(i)\n",
    "                    ans[start] = i\n",
    "                    if i > 1: ans[sec] = i\n",
    "                    if dfs(start + 1): return ans\n",
    "                    visited.remove(i)\n",
    "                    ans[start] = 0\n",
    "                    if i > 1: ans[sec] = 0\n",
    "            return None\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        res = [0 for _ in range(2 * n - 1)]\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        \n",
    "#         i: pos\n",
    "        def backtrace(i):\n",
    "            if i >= 2 * n - 1:\n",
    "                return True\n",
    "            if res[i] != 0:\n",
    "                return backtrace(i + 1)\n",
    "            \n",
    "            # x: number\n",
    "            for x in range(n, 0, -1):\n",
    "                if visited[x] == True:\n",
    "                    continue\n",
    "\n",
    "                if x == 1:\n",
    "                    visited[1] = True\n",
    "                    res[i] = 1\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    visited[1] = False\n",
    "                else:\n",
    "                    if i + x >= 2 * n - 1:\n",
    "                        continue\n",
    "                    if res[i] != 0 or res[i + x] != 0:\n",
    "                        continue\n",
    "                    res[i] = x\n",
    "                    res[i + x] = x\n",
    "                    visited[x] = True\n",
    "                    if backtrace(i + 1) == True:\n",
    "                        return True\n",
    "                    res[i] = 0\n",
    "                    res[i + x] = 0\n",
    "                    visited[x] = False\n",
    "            return False\n",
    "        \n",
    "        \n",
    "\n",
    "        backtrace(0)\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n * 2 - 1)\n",
    "        arr = SortedList(_ for _ in range(-n, -1))\n",
    "        used_1 = False\n",
    "\n",
    "        def traceback(idx):\n",
    "            if idx == n * 2 - 1:\n",
    "                return True\n",
    "            if ans[idx]:\n",
    "                return traceback(idx + 1)\n",
    "            for num in arr:\n",
    "                if idx - num < n * 2 - 1 and ans[idx - num] == 0:\n",
    "                    ans[idx] = ans[idx - num] = -num\n",
    "                    arr.discard(num)\n",
    "                    if traceback(idx + 1):\n",
    "                        return True\n",
    "                    arr.add(num)   # 回溯\n",
    "                    ans[idx] = ans[idx - num] = 0\n",
    "            nonlocal used_1\n",
    "            if not used_1:\n",
    "                ans[idx] = 1\n",
    "                used_1 = True\n",
    "                if traceback(idx + 1):\n",
    "                    return True\n",
    "                ans[idx] = 0   # 回溯\n",
    "                used_1 = False\n",
    "            return False\n",
    "        traceback(0)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n * 2 - 1)\n",
    "        arr = SortedList(_ for _ in range(-n, -1))\n",
    "        used_1 = False\n",
    "\n",
    "        def traceback(idx):\n",
    "            if idx == n * 2 - 1:\n",
    "                return True\n",
    "            if ans[idx]:\n",
    "                return traceback(idx + 1)\n",
    "            for num in arr:\n",
    "                if idx - num < n * 2 - 1 and ans[idx - num] == 0:\n",
    "                    ans[idx] = ans[idx - num] = -num\n",
    "                    arr.discard(num)\n",
    "                    if traceback(idx + 1):\n",
    "                        return True\n",
    "                    arr.add(num)   # 回溯\n",
    "                    ans[idx] = ans[idx - num] = 0\n",
    "            nonlocal used_1\n",
    "            if not used_1:\n",
    "                ans[idx] = 1\n",
    "                used_1 = True\n",
    "                if traceback(idx + 1):\n",
    "                    return True\n",
    "                ans[idx] = 0   # 回溯\n",
    "                used_1 = False\n",
    "            return False\n",
    "        \n",
    "        traceback(0)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n * 2 - 1)\n",
    "        arr = SortedList(_ for _ in range(-n, -1))\n",
    "        used_1 = False\n",
    "\n",
    "        def traceback(idx):\n",
    "            if idx == n * 2 - 1:\n",
    "                return True\n",
    "            if ans[idx]:\n",
    "                return traceback(idx + 1)\n",
    "            for num in arr:\n",
    "                if idx - num < n * 2 - 1 and ans[idx - num] == 0:\n",
    "                    ans[idx] = ans[idx - num] = -num\n",
    "                    arr.discard(num)\n",
    "                    if traceback(idx + 1):\n",
    "                        return True\n",
    "                    arr.add(num)   # 回溯\n",
    "                    ans[idx] = ans[idx - num] = 0\n",
    "            nonlocal used_1\n",
    "            if not used_1:\n",
    "                ans[idx] = 1\n",
    "                used_1 = True\n",
    "                if traceback(idx + 1):\n",
    "                    return True\n",
    "                ans[idx] = 0   # 回溯\n",
    "                used_1 = False\n",
    "            return False\n",
    "        \n",
    "        return ans if traceback(0) else []\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n * 2 - 1)\n",
    "        arr = SortedList(_ for _ in range(-n, -1))\n",
    "        used_1 = False\n",
    "\n",
    "        def traceback(idx):\n",
    "            if idx == n * 2 - 1:\n",
    "                return True\n",
    "            if ans[idx]:\n",
    "                return traceback(idx + 1)\n",
    "            for num in arr:\n",
    "                if idx - num < n * 2 - 1 and ans[idx - num] == 0:\n",
    "                    ans[idx] = ans[idx - num] = -num\n",
    "                    arr.discard(num)\n",
    "                    if traceback(idx + 1):\n",
    "                        return True\n",
    "                    arr.add(num)   # 回溯\n",
    "                    ans[idx] = ans[idx - num] = 0\n",
    "            nonlocal used_1\n",
    "            if not used_1:\n",
    "                ans[idx] = 1\n",
    "                used_1 = True\n",
    "                if traceback(idx + 1):\n",
    "                    return True\n",
    "                ans[idx] = 0   # 回溯\n",
    "                used_1 = False\n",
    "            return False\n",
    "        \n",
    "        traceback(0)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]: \n",
    "        if n==0:return []\n",
    "        if n==1:return [1]\n",
    "        result=[0]*(2*n-1)\n",
    "        remain=[i for i in range(n,0,-1)]\n",
    "    \n",
    "        for i in remain:\n",
    "            print(i)\n",
    "            sub_remain=remain.copy()\n",
    "            sub_remain.remove(i)\n",
    "            sub_result=result.copy()\n",
    "            sub_result[0]=i\n",
    "            sub_result[i]=i\n",
    "            sub_load=self.subDistanceSequence(sub_result,sub_remain)\n",
    "            if sub_load:\n",
    "                return sub_load\n",
    "    \n",
    "    def subDistanceSequence(self,result,remain):\n",
    "        if 0 not in result:return result\n",
    "        start = result.index(0)\n",
    "        sub_result=result.copy()\n",
    "        if result.count(0)==2 and len(remain)==1 and start+remain[0]<len(result) and result[start+remain[0]]==0 and remain[0]!=1:\n",
    "            sub_result[start]=remain[0]\n",
    "            sub_result[start+remain[0]]=remain[0]\n",
    "            if sub_result.count(0)==0:\n",
    "                return sub_result\n",
    "            else:\n",
    "                return []\n",
    "        elif result.count(0)==1 and len(remain)==1 and remain[0]==1:\n",
    "            sub_result[start]=remain[0]\n",
    "            return sub_result\n",
    "                   \n",
    "        for i in remain:\n",
    "            if start+i<len(result) and result[start+i]==0 and i!=1:\n",
    "                sub_result=result.copy()\n",
    "                sub_remain=remain.copy()\n",
    "                sub_result[start]=i\n",
    "                sub_result[start+i]=i\n",
    "                sub_remain.remove(i)\n",
    "                sub_load =self.subDistanceSequence(sub_result,sub_remain)\n",
    "                if sub_load:\n",
    "                    return sub_load\n",
    "            elif i==1:               \n",
    "                sub_result=result.copy()\n",
    "                sub_remain=remain.copy()\n",
    "                sub_result[start]=i\n",
    "                sub_remain.remove(i)\n",
    "                sub_load = self.subDistanceSequence(sub_result,sub_remain)\n",
    "                if sub_load:\n",
    "                    return sub_load\n",
    "            else:\n",
    "                continue\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def constructDistancedSequence(self, n: int) -> List[int]:\n",
    "        ans = [0] * (n * 2 - 1)\n",
    "        arr = SortedList(_ for _ in range(-n, -1))\n",
    "        used_1 = False\n",
    "\n",
    "        def traceback(idx):\n",
    "            if idx == n * 2 - 1:\n",
    "                return True\n",
    "            if ans[idx]:\n",
    "                return traceback(idx + 1)\n",
    "            for num in arr:\n",
    "                if idx - num < n * 2 - 1 and ans[idx - num] == 0:\n",
    "                    ans[idx] = ans[idx - num] = -num\n",
    "                    arr.discard(num)\n",
    "                    if traceback(idx + 1):\n",
    "                        return True\n",
    "                    arr.add(num)   # 回溯\n",
    "                    ans[idx] = ans[idx - num] = 0\n",
    "            nonlocal used_1\n",
    "            if not used_1:\n",
    "                ans[idx] = 1\n",
    "                used_1 = True\n",
    "                if traceback(idx + 1):\n",
    "                    return True\n",
    "                ans[idx] = 0   # 回溯\n",
    "                used_1 = False\n",
    "            return False\n",
    "        \n",
    "        if traceback(0):    return ans\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
